#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <set>

using namespace std;

  struct TreeNode {
      int val;
      TreeNode *left;
      TreeNode *right;
      TreeNode(int x) : val(x), left(NULL), right(NULL) {}
  };


static int pos[100000], in[100000];

TreeNode *construct(int posOrder[], int len1, int inOrder[], int len2)
{
    if (len1 == 0 || len2 == 0) return NULL;
    TreeNode *root = new TreeNode(posOrder[len1-1]);
    if (len1 == 1) return root;
    int index = 0;
    for (index = 0; index < len2; index++) {
	if (inOrder[index] == posOrder[len1-1]) break;
    }

    root->left = construct(posOrder, index, inOrder, index);
    root->right = construct(posOrder+index, len1 - index - 1, inOrder+1+index, len2-index-1);
    return root; 
}

class Solution {
public:
    TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder) {
	if (postorder.size() ==0) return NULL;
	int len1 = postorder.size(), len2 = inorder.size();
	for (int i = 0; i < postorder.size(); i++) 
	    pos[i] = postorder[i];
	for (int i = 0; i < inorder.size(); i++)
	    in[i] = inorder[i];
	TreeNode *root = construct(pos, len1, in, len2);
	return root;
    }
        
};


//pass all the test
int main(int argc, char **argv)
{

}
